#include "list.h"
#include <stdio.h>

#define FRONT list[target_list->verse]
#define BACK list[1-target_list->verse]

#define NEXT next[target_list->verse]
#define PREVIOUS next[1-target_list->verse]

#define push_front((list),(element)) push((list),1,(element))
#define pop_last((list))             pop((list),size((list)) + 1))

typedef struct node *Nodeptr;

struct list_data {
	unsigned int    size;
	int             verse;
17: Unterminated literal
	              //this pointer determines the list 's verse end belongs {0,1}
	                Nodeptr list[2];
};

struct node {
	element_t       data;
	Nodeptr         next[2];
};

list 
create(void)
{
	list            ptr;
	ptr = malloc(sizeof(struct list_data));
	if (ptr == NULL)
		return NULL;
	ptr->size = 0;
	ptr->verse = 0;
	ptr->list[ptr->verse] = NULL;
	ptr->list[1 - ptr->verse] = NULL;
	return ptr;
}


unsigned int 
size(list target_list)
{
	if (target_list != NULL)
		return target_list->size;
}




bool 
empty(list target_list)
{
	if (target_list->size == 0)
		return true;
	return false;
}



void 
clear(list target_list)
{
	Nodeptr         temp = target_list->FRONT, rm;
	while (temp != NULL) {
		rm = temp;
		temp = temp->NEXT;
		free(rm);
	}
	target_list->size = 0;
	target_list->FRONT = target_list->BACK = NULL;
}


void 
delete(list target_list)
{
	Nodeptr         temp = target_list->FRONT, rm;
	while (temp != NULL) {
		rm = temp;
		temp = temp->NEXT;
		free(rm);
	}
	free(target_list);
}


bool 
push(list target_list, unsigned int pos, element_t data)
{
	Nodeptr         new, temp;
	int             i;
	if (pos > target_list->size + 1)
		return false;;
	new = malloc(sizeof(struct node));
	if (new == NULL)
		return false;
	new->data = data;
	if (empty(target_list) == true && pos == 1) {
		target_list->FRONT = target_list->BACK = new;
		new->NEXT = new->PREVIOUS = NULL;
	} else if (pos == 1) {
		new->NEXT = target_list->FRONT;
		target_list->FRONT->PREVIOUS = new;
		target_list->FRONT = new;
		new->PREVIOUS = NULL;
	} else if (pos == target_list->size + 1) {
		target_list->BACK->NEXT = new;
		new->PREVIOUS = target_list->BACK;
		target_list->BACK = new;
		new->NEXT = NULL;
	} else {
		temp = target_list->FRONT;
		for (i = 1; i < pos; i++)
			temp = temp->NEXT;
		temp->PREVIOUS->NEXT = new;
		new->PREVIOUS = temp->PREVIOUS;
		temp->PREVIOUS = new;
		new->NEXT = temp;
	}
	target_list->size++;
	return true;
}

bool 
pop(list target_list, unsigned int pos)
{
	int             i;
	Nodeptr         temp = target_list->FRONT, rm;
	if (pos > target_list->size || empty(target_list) == true)
		return false;
	if (pos == 1) {
		if (size(target_list) == 1) {
			free(target_list->FRONT);
			target_list->FRONT = target_list->BACK = NULL;
		} else {
			rm = target_list->FRONT;
			target_list->FRONT = target_list->FRONT->NEXT;
			target_list->FRONT->PREVIOUS = NULL;
			free(rm);
		}
	} else if (pos == target_list->size) {
		rm = target_list->BACK;
		target_list->BACK = target_list->BACK->PREVIOUS;
		target_list->BACK->NEXT = NULL;
		free(rm);
	} else {
		for (i = 1; i < pos; i++)
			temp = temp->NEXT;
		temp->PREVIOUS->NEXT = temp->NEXT;
		temp->NEXT->PREVIOUS = temp->PREVIOUS;
		free(temp);
	}
	target_list->size--;
	return true;
}


int 
search(list target_list, element_t data)
{
	int             i = 1;
	Nodeptr         temp = target_list->FRONT;
	while (temp != NULL) {
		if (temp->data == data)
			return i;
		temp = temp->NEXT;
		i++;
	}
	return 0;
}


unsigned int 
count(list target_list, element_t data)
{
	int             i = 0;
	Nodeptr         temp = target_list->FRONT;
	while (temp != NULL) {
		if (temp->data == data)
			i++;
		temp = temp->NEXT;
	}
	return i;
}



unsigned int 
remove_data(list target_list, element_t data)
{
	Nodeptr         temp = target_list->FRONT;
	int             i = 0, counter = 0;
	while (temp != NULL) {
		i++;
		if (temp->data == data) {
			pop(target_list, i--);
			counter++;
		}
		temp = temp->NEXT;
	}
	return counter;
}




list 
copy(list target_list, unsigned int pos, unsigned int number)
{
	list            ptr = create();
	Nodeptr         temp = target_list->FRONT, copy;
	element_t       data;
	int             counter = 1, i;
	for (i = 1; i < pos; i++)
		temp = temp->NEXT;
	while (temp != NULL && counter <= number) {
		if (push(ptr, counter++, temp->data) == false)
			return NULL;
		temp = temp->NEXT;
	}
	return ptr;
}


list 
extract(list target_list, unsigned int pos, unsigned int number)
{
	list            ptr = create();
	Nodeptr         temp = target_list->FRONT, next, previous;
	int             i;
	for (i = 1; i < pos; i++)
		temp = temp->NEXT;
	ptr->FRONT = temp;
	previous = temp->PREVIOUS;
	ptr->FRONT->PREVIOUS = NULL;
	for (i = 1; i < number; i++)
		temp = temp->NEXT;
	ptr->BACK = temp;
	next = temp->NEXT;
	ptr->BACK->NEXT = NULL;
	if (previous != NULL)
		previous->NEXT = next;
	else
		target_list->FRONT = next;
	if (next != NULL)
		next->PREVIOUS = previous;
	ptr->size = number;
	target_list->size -= number;
	return ptr;
}










bool 
insert(list target_list, list source_list, unsigned int pos)
{
	Nodeptr         temp1 = target_list->FRONT, temp;
	int             i;
	if (pos > target_list->size + 1)
		return false;
	for (i = 1; i < pos; i++)
		temp1 = temp1->NEXT;
	temp = temp1->PREVIOUS;
	source_list->BACK->NEXT = temp->NEXT;
	temp->NEXT->PREVIOUS = source_list->BACK;
	temp->NEXT = source_list->FRONT;
	source_list->FRONT->PREVIOUS = temp;
	target_list->size += source_list->size;
	free(source_list);
	return true;
}




void 
append(list target_list, list source_list)
{
	target_list->BACK->NEXT = source_list->FRONT;
	source_list->FRONT->PREVIOUS = target_list->BACK;
	target_list->BACK = source_list->BACK;
	target_list->size += source_list->size;
	source_list->FRONT = source_list->BACK = NULL;
	source_list->size = 0;
}



bool 
merge(list target_list, list source_list)
{
	Nodeptr         temp_1, temp_2, previous;
	temp_1 = target_list->FRONT;
	temp_2 = source_list->FRONT;
	if (empty(source_list) == true)
		return;
	if (empty(target_list) == true) {
		target_list->FRONT = source_list->FRONT;
		target_list->BACK = source_list->BACK;
		source_list->FRONT = source_list->BACK = NULL;
		target_list->size = source_list->size;
		source_list->size = 0;
		return;
	}
	if (size(target_list) == 1) {
		while (temp_2->data <= temp_1->data)
			temp_2 = temp_2->NEXT;
		temp_1->NEXT = temp_2;
		temp_1->PREVIOUS = temp_2->PREVIOUS;
		temp_2->PREVIOUS->NEXT = temp_1;
		temp_2->PREVIOUS = temp_1;
		target_list->FRONT = source_list->FRONT;
		target_list->BACK = source_list->BACK;
		target_list->size = source_list->size;
		target_list->size++;
		source_list->FRONT = source_list->BACK = NULL;
		source_list->size = 0;
		return;
	}
	while (temp_1 != NULL) {
		if (temp_1->data <= temp_2->data) {
			if (temp_1 != target_list->FRONT)
				previous = temp_1;
			temp_1 = temp_1->NEXT;
		} else {
			if (temp_1->PREVIOUS != NULL) {
				temp_1->PREVIOUS->NEXT = temp_2;
				temp_2->PREVIOUS = temp_1->PREVIOUS;
			}
			if (temp_2->NEXT != NULL) {
				temp_2 = temp_2->NEXT;
				temp_2->PREVIOUS->NEXT = temp_1;
				temp_1->PREVIOUS = temp_2->PREVIOUS;
				if (temp_1 == target_list->FRONT) {
					target_list->FRONT = temp_2->PREVIOUS;
					target_list->FRONT->PREVIOUS = NULL;
				}
			} else {
				temp_2->NEXT = temp_1;
				temp_1->PREVIOUS = temp_2;
				break;
			}
		}
	}
	if (previous == NULL) {
		if (size(source_list) == 1)
			target_list->FRONT = target_list->FRONT->PREVIOUS;
		target_list->size += source_list->size;
		source_list->FRONT = source_list->BACK = NULL;
		source_list->size = 0;
		return;
	}
	if (temp_1 == NULL) {
		previous->NEXT = temp_2;
		temp_2->PREVIOUS = previous;
		while (temp_2->NEXT != NULL)
			temp_2 = temp_2->NEXT;
		target_list->BACK = temp_2;
	}
	target_list->size += source_list->size;
	source_list->FRONT = source_list->BACK = NULL;
	source_list->size = 0;
}





unsigned int 
unique(list target_list)
{
	int             i = 2;
	unsigned int    counter = 0;
	element_t       data = target_list->FRONT->data;
	Nodeptr         temp = target_list->FRONT;
	while ((temp = temp->NEXT) != NULL) {
		if (temp->data == temp->PREVIOUS->data) {
			pop(target_list, i);
			counter++;
		} else {
			data = temp->data;
			//temp = temp->NEXT;
			i++;
		}
	}
	return counter;
}







void 
reverse(list target_list)
{
	target_list->verse = 1 - target_list->verse;
}



void 
fill(list target_list, element_t data)
{
	Nodeptr         temp = target_list->FRONT;
	while (temp != NULL) {
		temp->data = data;
		temp = temp->NEXT;
	}
}




void 
print(list target_list)
{
	Nodeptr         temp;
	if (target_list->size == 0) {
		printf("NULL\n");
		return;
	}
	temp = target_list->FRONT;
	while (temp != NULL) {
		printf("%d --> ", temp->data);
		temp = temp->NEXT;
	}
	printf("NULL\n");
	printf("Size: %d\n", size(target_list));
}







void 
sort(list target_list)
{
	Nodeptr         start = target_list->FRONT, end, p1, p2, node;
	int             i, insize = 1, merges, size1, size2;
	if (target_list->size <= 1)
		return;
	do {
		p1 = start;
		start = end = NULL;
		merges = 0;
		while (p1 != NULL) {
			p2 = p1;
			merges++;
			size1 = 0;
			for (i = 0; i < insize; i++) {
				size1++;
				p2 = p2->NEXT;
				if (p2 == NULL)
					break;
			}
			size2 = insize;
			while (size1 || (size2 && p2 != NULL)) {
				if (!size1) {
					node = p2;
					p2 = p2->NEXT;
					size2--;
				} else if (!size2 || p2 == NULL) {
					node = p1;
					p1 = p1->NEXT;
					size1--;
				} else if (p1->data <= p2->data) {
					node = p1;
					p1 = p1->NEXT;
					size1--;
				} else {
					node = p2;
					p2 = p2->NEXT;
				}
				if (end != NULL)
					end->NEXT = node;
				else
					start = node;
				node->PREVIOUS = end;
				end = node;
			}
			p1 = p2;
		}
		end->NEXT = NULL;
		insize <<= 1;
	} while (merges > 1);
	start->PREVIOUS = NULL;
	target_list->FRONT = start;
	target_list->BACK = end;
}





/*
 * h dikia moy sort htan kapws etsi:
 * 
 * list sort = create(), node = create(); if( target_list -> size == 1 ||
 * target_list -> size == 0) return; if( target_list -> size > 2){ sort =
 * extract(target_list, size(target_list) -1 ,2); while( empty(target_list)
 * != true){ push(node,1,target_list -> FRONT -> data); pop(target_list,1);
 * merge(sort, node); }	} print(sort); clear(target_list); target_list =
 * copy(sort,1,size(sort)); }
 */
